package datastructure;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/18 10:54
 * @description:
 */

/**
 * 二叉树节点类，包含建树、打印双向链表和树形打印功能
 */
public class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }

    /**
     * 根据数组构建二叉搜索树
     */
    public static Node buildTree(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        Node root = new Node(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            insertNode(root, arr[i]);
        }
        return root;
    }

    /**
     * 向二叉搜索树插入节点
     */
    private static void insertNode(Node root, int val) {
        if (val < root.val) {
            if (root.left == null) {
                root.left = new Node(val);
            } else {
                insertNode(root.left, val);
            }
        } else {
            if (root.right == null) {
                root.right = new Node(val);
            } else {
                insertNode(root.right, val);
            }
        }
    }

    /**
     * 打印循环双向链表
     */
    public static void printDoublyList(Node head) {
        if (head == null) {
            System.out.println("空链表");
            return;
        }

        System.out.print("循环双向链表: ");
        Node current = head;
        do {
            System.out.print(current.val);
            System.out.print("(" + (current.left != null ? current.left.val : "null") +
                    "," + (current.right != null ? current.right.val : "null") + ")");
            System.out.print(" -> ");
            current = current.right;
        } while (current != head);
        System.out.println("(回到头部 " + head.val + ")");
    }

    /**
     * 打印树形结构的二叉树
     */
    public static void printTree(Node root) {
        if (root == null) {
            System.out.println("空树");
            return;
        }
        printTree(root, "", true);
    }

    /**
     * 辅助方法：递归打印树形结构
     * @param node 当前节点
     * @param prefix 前缀字符串
     * @param isLeft 是否为左子节点
     */
    private static void printTree(Node node, String prefix, boolean isLeft) {
        if (node.right != null) {
            printTree(node.right, prefix + (isLeft ? "│   " : "    "), false);
        }

        // 打印当前节点
        System.out.println(prefix + (isLeft ? "└── " : "┌── ") + node.val);

        if (node.left != null) {
            printTree(node.left, prefix + (isLeft ? "    " : "│   "), true);
        }
    }
}
